/**
 * 
 * 
 * 打家劫舍(二)
 * 
 * 描述

你是一个经验丰富的小偷，准备偷沿湖的一排房间，每个房间都存有一定的现金，为了防止被发现，你不能偷相邻的两家，即，如果偷了第一家，就不能再偷第二家，如果偷了第二家，那么就不能偷第一家和第三家。沿湖的房间组成一个闭合的圆形，即第一个房间和最后一个房间视为相邻。
给定一个长度为n的整数数组nums，数组中的元素表示每个房间存有的现金数额，请你计算在不被发现的前提下最多的偷窃金额。

数据范围：数组长度满足 
1
≤
n
≤
2
×
1
0
5
 
1≤n≤2×10 
5
  ，数组中每个值满足 
1
≤
n
u
m
s
[
i
]
≤
5000
 
1≤nums[i]≤5000 
 */
public class 打家劫舍2 {
    
    public static void main(String[] args) {
        
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int rob (int[] nums) {
        // write code here

        //第一家要偷
        int[] dp1 = new int[nums.length + 1];
        dp1[1] = nums[0];
        for (int i = 2; i < nums.length;
                i++) { //最后一家就不能偷了，因此nums[i-1]不遍历
            dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + nums[i - 1]);
        }

        //第一家不偷
        int[] dp2 = new int[nums.length + 1];
        dp2[1] = 0;
        for (int i = 2; i <= nums.length;
                i++) { //最后一家可以偷，因为nums[i-1]遍历
            dp2[i] = Math.max(dp2[i - 1], dp2[i - 2] + nums[i - 1]);
        }

        return Math.max(dp1[nums.length - 1], dp2[nums.length]);
    }
}
